100. Задача 3n + 1

Рассмотрим следующий алгоритм:

1. ввести n;

2. вывести n;

3. если n = 1, то остановиться;

4. если n нечетное, то n = 3 * n + 1;

5. иначе n = n / 2;

6. перейти на 2;

При n = 22 будет напечатана следующая последовательность чисел: 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1. По утверждению Коллатса приведенный алгоритм всегда остановится для любого значения n. Хотя утверждение до сих пор не доказано. Для заданного n можно определить количество чисел, которое будет напечатано алгоритмом. Это количество называется длиной цикла. Например, для n = 22 длина цикла равна 16. В задаче следует найти максимальное значение среди всех длин циклов чисел от i до j включительно.

Вход. Состоит из последовательности целых пар чисел i и j, каждое из которых больше 0 и меньше 10000. Каждая пара чисел задается в отдельной строке.

Выход. Для каждой входной пары чисел i и j вывести ее, а также максимальную длину цикла среди всех чисел между i и j включительно.

Пример входа

1 10

100 200

201 210

900 1000

Пример выхода

1 10 20

100 200 125

201 210 89

900 1000 174

РЕШЕНИЕ

элементарные вычисления

Анализ алгоритма

Упорядочим входные значения i и j (если i > j, то переставим их местами). Далее для каждого значения k (i £ k £ j) будем находить длину его цикла. Среди всех длин найдем максимальное значение.

Пример

Рассмотрим первый тест. Для n = 9 получим последовательность 9, 28, 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1. Ее длина равна 20 и будет максимально возможной среди всех длин циклов для чисел от 1 до 10.

Реализация алгоритма

Запишем функцию вычисления максимума двух чисел как макрос:

#define max(a,b) a > b ? a : b

Функция cycle_length ищет длину цикла для числа n.

int cycle_length(int n)

{

int cnt;

for(cnt = 1; n != 1; cnt++)

n = (n % 2) ? 3 * n + 1: n / 2;

return cnt;

}

Функция check находит максимальную длину цикла среди всех чисел от i до j.

int check(int i,int j)

{

int mx = 0;

for(; i <= j; i++)

mx = max (mx, cycle_length(i));

return mx;

}

Основной цикл программы. Запомним входные значения i и j в переменных itemp и jtemp. Если i > j, то переставим их местами. Для каждой входной пары выводим максимальную длину цикла.

while (scanf("%d %d",&i,&j) == 2)

{

itemp = i; jtemp = j;

if (i > j) tmp = i, i = j, j = tmp;

printf("%d %d %d\n",itemp, jtemp, check(i,j));

}